/*
 * @lc app=leetcode.cn id=140 lang=cpp
 *
 * [140] 单词拆分 II
 */
class Solution
{
public:
    vector<string> helper(string s,vector<string> &wordDict,unordered_map<string,vector<string>> &m)
    {
        if(m.count(s))
        {
            return m[s];
        }                                 
        if(s.empty())
        {
            return {""};
        }
        vector<string> res;
        for(string word:wordDict)
        {
            if(s.substr(0,word.size())!=word)
            {
                continue;
            }
            vector<string> rem = helper(s.substr(word.size()), wordDict, m);
            for(string str:rem)
            {
                res.push_back(word + (str.empty() ? "" : " ") + str);
            }
        }
        return m[s] = res;
    }
    vector<string> wordBreak(string s, vector<string> &wordDict)
    {
        unordered_map<string, vector<string>> m;
        return helper(s, wordDict, m);
    }
};
